package com.algorithm.ch1.cjm.math;

/**
 * 计数质数
 * 统计所有小于非负整数 n 的质数的数量。
 * 时间复杂度f(n^2),复杂度太高,leetcode过不了
 * @Author: Jie Ming Chen
 * @Date: 2018/9/13
 * @Version 1.0
 */
public class CountPrimes {

    public int countPrimes(int n) {

        int index = 2;
        int count = 0;

        boolean flag;
        while (index < n) {
            flag = isPrimes(index);
            if (flag) {
                count ++;
            }
            index++;
        }
        return count;
    }

    /**
     * 是否为质数
     * @param n
     * @return
     */
    private boolean isPrimes(int n) {

        if (n < 2) {
            return false;
        }

        int count = 0;
        for (int i = 2; i < n/i + 1; i++) {

            count++;

            if (n%i == 0) {
                return false;
            }
        }

        System.out.println(count);
        return true;
    }

    public static void main(String[] args) {

        long time = System.currentTimeMillis();

        int i = new CountPrimes().countPrimes(15000000);

        long time1 = System.currentTimeMillis();

        System.out.println(time1 - time);
    }

}
